package leetcode_1001_1100;

import java.util.Arrays;

public class LeeCode_1012 {
    public static void main(String[] args) {
        System.out.println(numDupDigitsAtMostN(100));
        System.out.println(numDupDigitsAtMostN(1000));
    }
    private static int numDupDigitsAtMostN(int n) {
        char[] s = Integer.toString(n).toCharArray();
        int len = s.length;
        int[][] memo = new int[len][1 << 10];
        for (int i = 0; i < len; i++) {
            Arrays.fill(memo[i], -1);
        }
        return n - f(s, 0, 0, true, false, memo);
    }
    private static int f(char[] s, int i, int mask, boolean isLimit, boolean isNum, int[][] memo){
        if (i == s.length)
            return isNum ? 1 : 0;
        if (!isLimit && isNum && memo[i][mask] != -1){
            return memo[i][mask];
        }
        int up = isLimit ? s[i] - '0' : 9, res = 0;
        if (!isNum)
            res += f(s, i + 1, mask, false, false, memo);
        for (int j = isNum ? 0 : 1; j <= up; j++) {
            if ((1 << j & mask) == 0)
                res += f(s, i + 1, mask | (1 << j), isLimit && up == j, true, memo);
        }
        if (!isLimit && isNum)
            memo[i][mask] = res;
        return res;
    }
}
